package com.clstu;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

/**
 * 马踏棋盘 算法体验
 */
public class HorseChessBoard {
    //定义一些属性
    private static int rows = 6;//行数
    private static int cols = 6;//列数
    private static int[][] chessBoard = new int[rows][cols];//棋盘
    private static boolean[] visited = new boolean[rows*cols];//标记某个位置是否走过
    private static boolean finished = false;//是否全部走完

    public static void main(String[] args) {

        //起始点
        int x=2;
        int y=2;
        //测试耗时,体现不同算法的效率
        long l = System.currentTimeMillis();
        travelChessBoard(chessBoard,x-1,y-1,1);
        long r = System.currentTimeMillis();
        System.out.println("耗时:"+(r-l)+"ms");

        //输出当前棋盘的情况(走法不唯一!!!)
        for (int i = 0; i < chessBoard.length; i++) {
            for (int j = 0; j < chessBoard[i].length; j++) {
                System.out.print(chessBoard[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.println(finished);

    }

    //优化思路:减少回溯的次数!!!!先走回溯次数少的点,即可以走到下一个位置的个数少的点
    //编写方法将周围的点ps 按照可以走的下一跳的个数从小到大排序
    public static void sort(ArrayList<Point> ps){
        ps.sort(new Comparator<Point>() {//根据自己的比较器排序
            @Override
            public int compare(Point o1, Point o2) {
                return next(o1).size() - next(o2).size();//把周围的点按照可以走的位置个数从小到大排序
            }
        });
    }

    //编写最核心的算法,遍历棋盘,如果遍历完成 finished=true,chessBoard记录具体是哪一步走到那个位置
    public static void travelChessBoard(int[][] chessBoard,int x,int y,int step){
        //先把step标记的到chesBoard
        chessBoard[y][x]=step;
        //把这个位置设置为已经访问
        visited[y*cols+x] = true;
        //遍历每个周围的点
        ArrayList<Point> ps = next(new Point(x, y));

        //排序,减少回溯次数(优化效率的核心!!!!)
        sort(ps);

        while (!ps.isEmpty()){//如果周围的点没有删完
            //取出一个点,同时删除它(遍历一遍就没有用了)
            Point p = ps.remove(0);
            //判断改位置是否走过,如果没有走过,则递归遍历
            if(!visited[p.y*cols+p.x]) {
                travelChessBoard(chessBoard, p.x, p.y, step + 1);
            }
        }
        //当退出while循环的时候,判断是否走完//step==rows*cols 代表走完
        if(step<rows*cols && !finished){//没走完的话(走不完就回溯重走,换下一个点)
            //重置(如果走不完也是递归重置)
            chessBoard[y][x]=0;
            visited[y*cols+x]=false;
        }else {//走完了的情况(走完了回溯的话就不用重走,因为所有visited=true)
            finished = true;//代表走完
        }
    }

    //编写方法,得到当前位置可以走的下一步的所有位置(正常来说一个马的周围通常有8个位置可以走,判断哪些可以走)
    public static ArrayList<Point> next(Point curPoint){
        ArrayList<Point> points = new ArrayList<>();//存放可以走的下一步的所有点
        Point p = new Point();//便于new 一个点放入集合中
        //判断位置5是否可以走
        if((p.x=curPoint.x-2)>=0&&(p.y=curPoint.y-1)>=0) points.add(new Point(p));//必须new
        //判断位置6是否可以走
        if((p.x=curPoint.x-1)>=0&&(p.y=curPoint.y-2)>=0) points.add(new Point(p));
        //判断位置7是否可以走
        if((p.x=curPoint.x+1)<cols&&(p.y=curPoint.y-2)>=0) points.add(new Point(p));
        //判断位置0是否可以走
        if((p.x=curPoint.x+2)<cols&&(p.y=curPoint.y-1)>=0) points.add(new Point(p));
        //判断位置1是否可以走
        if((p.x=curPoint.x+2)<cols&&(p.y=curPoint.y+1)<rows) points.add(new Point(p));
        //判断位置2是否可以走
        if((p.x=curPoint.x+1)<cols&&(p.y=curPoint.y+2)<rows) points.add(new Point(p));
        //判断位置3是否可以走
        if((p.x=curPoint.x-1)>=0&&(p.y=curPoint.y+2)<rows) points.add(new Point(p));
        //判断位置4是否可以走
        if((p.x=curPoint.x-2)>=0&&(p.y=curPoint.y+1)<rows) points.add(new Point(p));
        return points;
    }



}
